package com.pan.alg.niuke.link;

import java.util.ArrayList;
import java.util.List;

import static java.util.Collections.swap;

/**
 * 描述
 * 给定一个单链表，请设定一个函数，将链表的奇数位节点和偶数位节点分别放在一起，重排后输出。
 * 注意是节点的编号而非节点的数值。
 *
 * 数据范围：节点数量满足 0 \le n \le 10^50≤n≤10
 * 5
 *  ，节点中的值都满足 0 \le val \le 10000≤val≤1000
 * 要求：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)
 */
public class LinkOddEvenList {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param head ListNode类
     * @return ListNode类
     */
    public ListNode oddEvenList (ListNode head) {
        if(null==head){
            return head;
        }
        // write code here
        List<ListNode> oddList = new ArrayList<>();
        List<ListNode> evenList = new ArrayList<>();

        List<ListNode> arrLink = ListNodeUtil.transListNode2List(head);
        for (int i = 0; i < arrLink.size(); i++) {
            if((i+1)%2==0){
                evenList.add(arrLink.get(i));
            }else{
                oddList.add(arrLink.get(i));
            }
            arrLink.get(i).next=null;
        }

        if(oddList.isEmpty()){
            return ListNodeUtil.transListNode2LinkNode(evenList);
        }else if(evenList.isEmpty()){
            return ListNodeUtil.transListNode2LinkNode(oddList);
        }else{
            ListNode odd = ListNodeUtil.transListNode2LinkNode(oddList);
            ListNode even = ListNodeUtil.transListNode2LinkNode(evenList);
            oddList.get(oddList.size()-1).next=even;
            return odd;
        }
    }

    public static List<ListNode> quickSortListNode(List<ListNode> arrLink, int l, int r) {
        if(l>=r){
            return arrLink;
        }

        int index = partion(arrLink,l,r);

        quickSortListNode(arrLink,l,index-1);
        quickSortListNode(arrLink,index+1,r);

        return arrLink;
    }

    public static int partion(List<ListNode> arrLink, int l, int r) {

        ListNode compare = arrLink.get(l);
        int lastMin = l;
        for (int i = l+1; i <=r ; i++) {
            if(arrLink.get(i).val<compare.val){
                lastMin++;
                swap(arrLink,i,lastMin);
            }
        }
        swap(arrLink,l,lastMin);
        return lastMin;
    }
}
